Trong chuyến đi đầu tiên đến châu Mỹ do Tây Ban Nha tài trợ vào năm 1492, Cristoforo Colombo đã đi thuyền về phía nam từ Bahamas để khám phá bờ biển phía đông bắc Cuba và bờ biển phía bắc Hispaniola. Colombo vốn đang tìm đường đến Ấn Độ, tin rằng hòn đảo này là một bán đảo của châu Á lục địa.[20][21] Lần đầu tiên một con tàu Tây Ban Nha đến gần đảo là vào ngày 27 tháng 10 năm 1492 có lẽ là tại Bariay, tỉnh Holguín ở điểm phía đông hòn đảo.[22]

Trong chuyến hành trình thứ hai vào năm 1494, Colombo đi dọc theo bờ biển phía nam của hòn đảo và đổ bộ tại nhiều vịnh nhỏ khác nhau bao gồm cả nơi mà sau này trở thành vịnh Guantánamo. Với sắc lệnh của Giáo Hoàng 1493, Giáo hoàng Alexanđê VI đã chỉ huy Tây Ban Nha chinh phục, thuộc địa hóa và cải đạo những kẻ ngoại giáo của Tân Thế giới sang Công giáo.[23] Khi đến nơi, Colombo quan sát những ngôi nhà của người Taíno, mô tả chúng là "trông giống như những chiếc lều trong trại. Tất cả đều bằng cành cọ, được xây dựng rất đẹp".[24]

Người Tây Ban Nha bắt đầu lập ra các khu định cư lâu dài trên đảo Hispaniola phía đông Cuba ngay sau khi Colombo đến Caribe. Tuy nhiên, bờ biển Cuba chưa được người châu Âu lập bản đồ đầy đủ cho đến khi Sebastián de Ocampo hoàn thành sứ mệnh này vào năm 1508.[25] Năm 1511, Diego Velázquez de Cuéllar khởi hành từ Hispaniola để thành lập khu định cư đầu tiên của người Tây Ban Nha ở Cuba theo chỉ thị từ Tây Ban Nha là phải chinh phục hòn đảo. Khu định cư tọa lạc ở Baracoa. Những người định cư mới đã phải đối mặt với sự phản kháng gay gắt từ người Taíno bản địa. Ban đầu, người Taíno được lãnh đạo bởi cacique (thủ lĩnh) Hatuey đã đi khỏi Hispaniola để thoát khỏi sự cai trị tàn bạo của Tây Ban Nha trên hòn đảo đó. Sau một chiến dịch du kích kéo dài, Hatuey và các thủ lĩnh liên tiếp bị bắt và bị thiêu sống. Trong vòng ba năm, người Tây Ban Nha đã giành được quyền kiểm soát hòn đảo. Năm 1514, một khu định cư được thành lập tại nơi mà sau này trở thành La Habana.

Giáo sĩ Bartolomé de las Casas đã quan sát một số vụ thảm sát do quân xâm lược khởi xướng khi người Tây Ban Nha tràn qua hòn đảo, đặc biệt là vụ thảm sát người Caonao gần Camagüey. Theo lời kể của ông, khoảng ba nghìn dân làng đã đến Manzanillo để tiếp đón người Tây Ban Nha bằng bánh mì, cá và các loại thực phẩm khác và "không hề có ý khiêu khích nhưng lại bị giết thịt".[26] Các nhóm dân bản địa sống sót chạy trốn lên núi hoặc các hòn đảo nhỏ xung quanh trước khi bị bắt và buộc phải chuyển đến các khu bảo tồn. Một khu bảo tồn như vậy là Guanabacoa, nay là vùng ngoại ô La Habana.[27]

Năm 1513, Fernando II của Aragon ban hành sắc lệnh thiết lập hệ thống thuộc địa encomienda thống nhất trên toàn châu Mỹ thuộc Tây Ban Nha. Thống đốc Cuba Velázquez chuyển từ Baracoa đến Santiago de Cuba và được giao nhiệm vụ phân chia cả đất đai và các dân tộc bản địa cho các nhóm trên khắp thuộc địa mới. Tuy nhiên, kế hoạch này đã không thành công vì người bản xứ hoặc không chống chọi nổi với các bệnh mang đến từ Tây Ban Nha như bệnh sởi và bệnh đậu mùa hoặc đơn giản là từ chối làm việc và chạy trốn vào núi.[22] Việc thiếu hụt lao động đã làm khó các khu định cư nông nghiệp mới, các Conquistador phải tìm kiếm nô lệ từ các hòn đảo xung quanh và trên lục địa. Tuy nhiên, những người mới đến cũng lại theo chân những người bản địa bằng cách trốn vào vùng hoang dã hoặc chết vì bệnh tật.[22]

Bất chấp mối quan hệ khó khăn giữa người bản xứ và thực dân châu Âu mới, vẫn có một số mối quan hệ hợp tác. Người Tây Ban Nha đã được người bản xứ chỉ cho cách trồng thuốc lá và tiêu thụ nó dưới dạng xì gà. Cũng có nhiều liên kết giữa thực dân Tây Ban Nha (phần lớn là nam giới) và phụ nữ bản địa. Các nghiên cứu thời hiện đại đã tiết lộ dấu vết của DNA biểu hiện các đặc điểm thể chất tương tự như các bộ lạc Amazon ở các cá nhân trên khắp Cuba,[28] mặc dù nền văn hóa và văn minh của người dân bản địa đã bị phá hủy phần lớn sau năm 1550. Theo Luật mới của Tây Ban Nha năm 1552, người Cuba bản địa được giải phóng khỏi encomienda và bảy thị trấn dành cho người bản địa được thành lập. Có những gia đình hậu duệ người Cuba (người Taíno] bản địa ở một số nơi, chủ yếu ở miền đông Cuba. Cộng đồng bản địa tại Caridad de los Indios, Guantánamo là một trong những hạt nhân như vậy. Một hiệp hội các gia đình người bản địa ở Jiguani, gần Santiago cũng đang hoạt động. Cư dân bản địa địa phương cũng để lại dấu ấn của họ trên ngôn ngữ này, với khoảng 400 thuật ngữ và địa danh tiếng Taíno còn tồn tại cho đến ngày nay. Bản thân tên Cuba , La Habana , Camagüey và nhiều tên khác có nguồn gốc từ tiếng Taíno Cổ điển, các từ bản địa như tobacco (thuốc lá) , hurricane (bão) và canoe đã được chuyển sang tiếng Anh và được sử dụng đến ngày nay.[27]